//
// Created by yangchao on 2022/5/12.
// 75. 颜色分类: https://leetcode.cn/problems/sort-colors/
//

#include <vector>
using namespace std;

//原地排序：空间复杂度为O(1)
class SortColors{
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        if (len < 2) return;
        int zero = 0;
        int two = len;
        int i = 0;
        while (i < two) {
            if (nums[i] == 0) {
                swap(nums[zero],nums[i]);
                zero++;
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                two--;
                swap(nums[i],nums[two]);
            }
        }
    }
};

